window.onload = function () {
  /**
   * 64. 最小路径和
   */
  console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))

  /**
   * 647. 回文子串
   */
  console.log(countSubstrings('abc'))

  /**
   * 312. 戳气球
   */
  console.log(maxCoins([3, 1, 5, 8]))
}

/**
 * 64. 最小路径和
 * @param {number[][]} grid
 * @return {number}
 */
const dirs = [[1, 0], [0, 1]]
var minPathSum = function (grid) {
  const MAX_INT = Math.pow(2, 31) - 1
  const m = grid.length, n = grid[0].length
  const memo = new Array(m).fill(0).map(() => new Array(n).fill(MAX_INT))

  const dfs = (row, col) => {
    if (row == m - 1 && col == n - 1) return grid[row][col]

    if (memo[row][col] != MAX_INT) return memo[row][col]

    let minPathSum1 = MAX_INT
    for (const dir of dirs) {
      const nextRow = row + dir[0]
      const nextCol = col + dir[1]
      if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) continue
      const childMinPathSum = dfs(nextRow, nextCol)
      minPathSum1 = Math.min(minPathSum1, childMinPathSum)
    }

    memo[row][col] = minPathSum1 + grid[row][col]
    return memo[row][col]
  }

  return dfs(0, 0)
};

/**
 * 647. 回文子串
* @param {string} s
* @return {number}
*/
var countSubstrings = (s) => {
  let count = 0;
  const len = s.length;

  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false);
  }

  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (i == j) {
        dp[i][j] = true;
        count++;
      } else if (j - i == 1 && s[i] == s[j]) {
        dp[i][j] = true;
        count++;
      } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        count++;
      }
    }
  }
  return count;
};

/**
 * 312. 戳气球
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
  let n = nums.length;
  // 添加两侧的虚拟气球
  let points = [1, ...nums, 1];
  let dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0));
  // 最后一行开始遍历,从下往上
  for (let i = n; i >= 0; i--) {
    // 从左往右
    for (let j = i + 1; j < n + 2; j++) {
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          points[j] * points[k] * points[i] + dp[i][k] + dp[k][j]
        );
      }
    }
  }
  return dp[0][n + 1];
};


